package day_2022_7_to_8.day48;

/**
 * @author haomin
 * @date 2022/08/31 15:26
 **/
public class Day46_3_Offer25_MergeTwoLists {
    // 迭代
    class Solution {
        public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
            if(l1 == null) return l2;
            if(l2 == null) return l1;

            ListNode dummyHead = new ListNode(-1);
            ListNode cur = dummyHead;
            while(l1 != null && l2 != null){
                if(l1.val < l2.val){
                    cur.next = l1;
                    cur = l1;
                    l1 = l1.next;
                }else{
                    cur.next = l2;
                    cur = l2;
                    l2 = l2.next;
                }
            }
            if(l1 == null) cur.next = l2;
            if(l2 == null) cur.next = l1;
            return dummyHead.next;
        }
    }
    // 递归
    class Solution2 {
        public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
            if(l1 == null) return l2;
            if(l2 == null) return l1;

            if(l1.val < l2.val){
                l1.next = mergeTwoLists(l1.next, l2);
                return l1;
            }else {
                l2.next = mergeTwoLists(l1, l2.next);
                return l2;
            }
        }
    }
}